When a terminal connects to a network, particularly an ad hoc network such as a network of mobile devices, it needs to determine a suitable network address to facilitate the communication with other terminals or nodes connected to the network. With the IP (Internet Protocol) there are various facilities to allow a terminal to determine a suitable network address. In IPv4 (Internet Protocol version 4) addresses are becoming scarce due to the way in which addresses are allocated and the increasing demand for new addresses. Allocation must be carefully controlled and so addresses are either manually allocated to a terminal by an administrator or they may be allocated using DHCP (Dynamic Host Configuration Protocol). DHCP requires a DHCP server which maintains a database of available addresses. When a terminal connects to the network, it requests an available address from the DHCP server. The DHCP server then allocates an IP address to the network terminal. However, this technique requires a DHCP server to be available to the newly connecting terminal and also requires the DHCP server to maintain a list of available addresses. In order to provide high flexibility and the ability for a new terminal to connect to networks freely then a large number of DHCP servers would be needed, each with a store of unique available addresses. An ad-hoc network is essentially one without infrastructure, in which case DHCP is not possible. Making a DHCP server available would require infrastructure and so limit the flexibility of an ad-hoc network.
In IPv6, a later version of the IP protocol, the potential number of addresses available is vastly greater than that under IPv4. Whilst this overcomes the problem of the limitation of the number of potential addresses available, it is still inconvenient to have a separate server to store available addresses to be allocated to a terminal upon request. It is therefore desirable to allow a terminal to configure itself with an IP address without the need for a separate server to allocate addresses.
Various systems have been proposed for allowing IP address autoconfiguration in ad hoc networks. In the paper entitled “IP Address Autoconfiguration for Ad Hoc Networks” by Charles E Perkins et al for the ‘Mobile Ad Hoc Networking Group’ of the Internet Engineering Task Force (IETF) [14 Nov. 2001], a mechanism is described by which a terminal or node in an ad hoc network may autoconfigure itself with an IP address which is unique throughout the connected portion of the ad hoc network.
The Perkins et al document describes a system in which a terminal performing autoconfiguration picks two addresses, a temporary one and the tentative address which it wishes to use. The temporary address is used only briefly in order to determine the uniqueness of the tentative address. In order to determine whether the tentative address is unique, the terminal sends out an address request (AREQ). If it receives an address reply (AREP) then it knows that the tentative address is not unique. If no AREP is received, the tentative address is deemed to be unique. For IPv6 the AREQ is a modified neighbour solicitation (NS) message. The neighbour solicitation message is modified with a flag to indicate that it is acting as part of a duplicate address detection (DAD) operation rather than its normal function as a neighbour communication message. Consequently when a neighbour solicitation message is received in which the flag is set, the message is passed on by a node as opposed to normal where the message only travels to neighbours that are one hop away from it.
A terminal which receives a neighbour solicitation message indicating a tentative address which corresponds to its own address issues an address reply (AREP) message in the form of a modified neighbour advertisement (NA) message. The neighbour advertisement message is modified with a flag similar to the neighbour solicitation message to indicate that the neighbour advertisement message is acting as part of a duplicate address detection (DAD) process. This NA message is similarly passed from node to node rather than simply only travelling one hop to its immediate neighbours. In this way, the modified NA message will be distributed back to the original sender of the NS message so that it knows that the tentative address is not unique. The tentative address is initially selected by providing a suitable prefix from a site-local prefix and appending to that a number from the terminal itself. This may be a random number or a number based upon some characteristic of the terminal such as its MAC number or its extended universal identity number (EUI-64). Whilst these numbers are intended to be unique to a terminal or its network card, there is still a possibility that an address formed in this way will not be unique.
Perkins et al indicates that when a network coalesces with another network, duplicate address detection (DAD) would need to be performed although no technique for detecting when network coalescence takes place or how the initiation of DAD would take place, is indicated in the document.
The paper entitled “IPv6 Autoconfiguration in Large Scale Mobile Ad Hoc Networks” by Kilian Weniger and Martina Zitterbart of the University of Karlsruhe from ‘Proceedings of European Wireless’ (2002) proposes a hierarchical approach to address autoconfiguration. The paper considers the applicability of IPv6 and its stateless address autoconfiguration to large-scale mobile ad hoc networks. Nodes in mobile ad hoc networks are integrated hosts and routers. As a consequence, all nodes execute all router functionalities. In order to apply IPv6 stateless address autoconfiguration in environments other than single broadcast links, routers which issue router advertisements (RA) are needed. However, during duplicate address detection (DAD), it is necessary to flood the network with the messages. This flooding leads to congestion and, as the size of the network increases, the congestion becomes unacceptable. Weniger et al describes a system which attempts to limit flooding by each terminal defining its broadcast link as the group of nodes that are less than a certain number of hops away from it. To achieve this, a hierarchy is established using a leader node that configures a group of its neighbour nodes by issuing router advertisements. In this way, the neighbour nodes do not need to carry out their router functions and the associated outputting of RA messages and so the necessary traffic is reduced. However, the initial election and subsequent re-election of the leaders is complex and duplicate address detection has to be performed periodically to deal with network partitioning and merging which adds further complexity to the protocol.
Therefore there is a need to provide a network protocol which allows for stateless address autoconfiguration which avoids complex hierarchical structure and which is able to deal with the dynamic nature of mobile networks in particular where network partitioning and merging occurs regularly. In addition, it is preferable to provide an address selection technique which provides site-local addresses rather than link-local addresses to reduce the likelihood of address duplication.